package com.wrial.offer;
/*
 * @Author  Wrial
 * @Date Created in 12:11 2020/4/2
 * @Description 最小的k个数  也就是TopN问题
 */

public class FaceTest_40 {

    // topN问题 使用堆排序或者是快排
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] ans = new int[k];
        int currentSize = arr.length;
        // 调整第一个非叶子节点
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapAdjust(arr, arr.length, i);
        }
        // 拿出k个小值
        for (int i = 0; i < k; i++) {
            ans[i] = arr[0];
            arr[0] = arr[currentSize - 1];
            currentSize--;
            heapAdjust(arr, currentSize, 0);
        }

        return ans;
    }

    // 调整，保证堆的根节点总是最小的  调整第i个的位置
    private void heapAdjust(int[] arr, int length, int i) {
        int smallerIndex = 2 * i + 1;
        while (smallerIndex < length) {
            // 如果有右节点
            if (smallerIndex + 1 < length) {
                smallerIndex = arr[smallerIndex] > arr[smallerIndex + 1]
                        ? smallerIndex + 1 : smallerIndex;
            }
            // 交换
            if (arr[i] > arr[smallerIndex]) {
                swap(arr, i, smallerIndex);
                // 由于调整后对左右子树改变了，需要进一步调整
                i = smallerIndex;
                smallerIndex = 2 * i + 1;
            } else {
                // 没有交换就break
                break;
            }
        }


    }

    private void swap(int[] arr, int i, int smallerIndex) {
        int temp = arr[i];
        arr[i] = arr[smallerIndex];
        arr[smallerIndex] = temp;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{0,1,2,1};
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
       int[] ans = new FaceTest_40().getLeastNumbers(arr, 1);
        for (int an : ans) {
            System.out.print(an+" ");
        }
    }
}
